package leetcode.hot100;
import java.util.*;

public class Solution399 {

    public static void main(String[] args) {

        List<List<String>> equations = new ArrayList<>();
        equations.add(new ArrayList<>(Arrays.asList("a","b")));
        equations.add(new ArrayList<>(Arrays.asList("b","c")));
        double[] values = new double[]{2.0,3.0};
        List<List<String>> queries = new ArrayList<>();
        queries.add(new ArrayList<>(Arrays.asList("a","c")));
        queries.add(new ArrayList<>(Arrays.asList("b","a")));
        queries.add(new ArrayList<>(Arrays.asList("a","e")));
        queries.add(new ArrayList<>(Arrays.asList("a","a")));
        queries.add(new ArrayList<>(Arrays.asList("x","x")));
        System.out.println(new Solution399().calcEquation(equations,values,queries));
    }


    /*---------------------------------------方法1：并查集-------------------------------------------*/

    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {

        //第一步：根据equations构建并查集
        UnionSet us = new UnionSet(equations.size()*2);
        HashMap<String,Integer> nameToId = new HashMap<>(); //为了方便后续操作，把节点名称映射为数字下标
        int id = 0;
        for (int i = 0; i < values.length; i++) {
            String x = equations.get(i).get(0);
            String y = equations.get(i).get(1);
            if(!nameToId.containsKey(x)) nameToId.put(x,id++);
            if(!nameToId.containsKey(y)) nameToId.put(y,id++);
            us.union(nameToId.get(x),nameToId.get(y),values[i]);
        }

        //第二步：处理queries
        double[] res = new double[queries.size()];
        for (int i = 0; i < queries.size(); i++) {
            Integer x = nameToId.get(queries.get(i).get(0));
            Integer y = nameToId.get(queries.get(i).get(1));
            if(x==null||y==null) res[i] = -1.0;
            else res[i] = us.ratioOf(x,y);
        }
        return res;
    }

    /*---------------------------------------方法2：构建图找路径-------------------------------------------*/


    public double[] calcEquation1(List<List<String>> equations, double[] values, List<List<String>> queries) {
        //构建有向图，寻找一条路径，将路径上的值相乘即可，为方便遍历使用邻接表表示
        HashMap<String, LinkedList<GraphNode>> graph = new HashMap<>();
        for (int i = 0; i < values.length; i++) {
            String start = equations.get(i).get(0);
            String end = equations.get(i).get(1);
            double edgeWeight = values[i];
            //开始节点和结束节点的邻接链表
            LinkedList<GraphNode> startAdj = graph.getOrDefault(start, new LinkedList<>());
            LinkedList<GraphNode> endAdj = graph.getOrDefault(end, new LinkedList<>());
            startAdj.add(new GraphNode(end,edgeWeight));
            endAdj.add(new GraphNode(start,1/edgeWeight));
            graph.put(start,startAdj);
            graph.put(end,endAdj);
        }
        //构建visit标志
        HashMap<String,Boolean> visited = new HashMap<>();
        //寻找路径可以用dfs
        double[] res = new double[queries.size()];
        for (int i = 0; i < queries.size(); i++) {
            String start = queries.get(i).get(0);
            String end = queries.get(i).get(1);
            //path记录路径上的边权
            ArrayList<Double> path = new ArrayList<>();
            //重置visited为false
            for (String nodeName: graph.keySet()) {
                visited.put(nodeName,false);
            }
            //
            dfs(graph,start,end,path,visited);
            if(path.size()==0) res[i] = -1.0;
            else {
                res[i] = 1.0;
                for(double edgeWeight : path){
                    res[i] *= edgeWeight;
                }
            }
        }
        return res;
    }


    public boolean dfs(HashMap<String, LinkedList<GraphNode>> graph,String start,String target,
                       ArrayList<Double> path,HashMap<String,Boolean> visited){
        if(!visited.containsKey(start)||visited.get(start)) return false; //不存在节点或者已经访问过了
        if(start.equals(target)){
            path.add(1.0); //如果start==end,path不应为空；如果不相等，最后结果乘1也没影响
            return true; //找到了
        }
        visited.put(start,true);
        for (GraphNode curNode : graph.get(start)) {
            path.add(curNode.edgeWeight);
            if(dfs(graph, curNode.nodeName, target, path, visited)) return true;
            path.remove(path.size()-1);
        }
        visited.put(start,false);
        return false;
    }
}

class GraphNode{
    double edgeWeight;
    String nodeName;

    public GraphNode(String nodeName, double edgeWeight) {
        this.edgeWeight = edgeWeight;
        this.nodeName = nodeName;
    }
}

class UnionSet{

    int[] parent;
    double[] weight; //parent表示每个节点的父节点，weight代表等于多少倍的根节点

    public UnionSet(int n){
        parent = new int[n];
        weight = new double[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            weight[i] = 1.0d;
        }
    }

    //查找x的根节点并压缩x到根的路径
    public int findAndCompress(int x){
        if(x==parent[x]) return x;
        int oldParent = parent[x];
        parent[x] = findAndCompress(parent[x]);
        weight[x] *= weight[oldParent];
        return parent[x];
    }

    //合并两个集合:x=y*value
    public void union(int x, int y, double value){
        int xRoot = findAndCompress(x);
        int yRoot = findAndCompress(y);
        if(xRoot==yRoot) return;
        parent[xRoot] = yRoot;
        weight[xRoot] = weight[y]*value/weight[x];
    }

    //检查两元素是否在同一个集合，在则返回比值，不在返回-1.0
    public double ratioOf(int x, int y){
        int xRoot = findAndCompress(x);
        int yRoot = findAndCompress(y);
        if(xRoot==yRoot) return weight[x]/weight[y];
        return -1.0d;
    }
}